1. Field of the Invention
The present invention relates to a datagram transfer apparatus and a datagram transfer method for executing a transfer destination determining process.
2. Description of the Related Art
Conventionally, the allocation of a load to a plurality of resources has been mainly developed in a field such as a load distribution within a client side proxy server firm on Web and selection of a rendezvous point in PIM-SM (Protocol Independent Multicast-Sparse Mode) that is one of multicast routing protocols. On the other hand, recently, the quick increase of Internet traffic makes data transmission in sufficient traffic difficult, even if only a TDM (Time Division Multiplexing) rate is increased in a link between routers, as in OC (Optical Carrier)-48 or OC-192. For this reasons a configuration in which a plurality of DWDM (Dense Wavelength Division Multiplexer) channels are set in parallel is already introduced in North America.
FIG. 1 shows an example of the configuration in which a plurality of DWDM channels are set in parallel. Referring to FIG. 1, data transfer apparatuses 100a to 100f have optical wave communication apparatuses 101a to 101f, respectively. The data transfer apparatuses 100a to 100f are connected by the plurality of optical wave channels through the optical wave communication apparatuses so that an optical wave link is established. Therefore, in FIG. 1, a router receiving a packet needs to select a router to be next transferred and additionally to select one of a plurality of paths connected to the selected router.
As another technique for data transmission in a sufficient throughput, an MPLS (MultiProtocol Label Switching) based traffic engineering is studied. This technique is aimed at optimization of load balance in a network or speed-up of a fault recovery in a complicated IP backbone network to which a recent topology technique is applied. For this purpose, a plurality of label switching paths (LSP) are set between an input router and an output router in the same area to accurately control a load without conventional destination address based transfer and a shortest path routing. FIG. 2 shows the configuration of a network of the MPLS-based traffic engineering as mentioned above. Referring to FIG. 2, two routers are used as an input router and an output router and two of LSP1 and LSP2 are allocated between the input router and output router. Also, a distribution ratio allocated to each LSP is set such that LSP1:LSP2=60%:40%. Therefore, a stream that reaches the input router and is transferred to the output router is divided to have the ratio of 3 to 2.
In the above next generation network, one or more paths are set for the same next hop router. For this reason, if different paths are allocated to packets forming the same flow, delay times in packet transmission are different for the respective routes. Therefore, there may be a case that an order of packets to be received by an end user is different from an order at a transmission source. In such a case, a re-transmission process may be carried out when packets including TCP segments such as a TCP (Transmission Control Protocol) session are transmitted through different paths so that the order is changed. The thus-retransmitted traffic is the additionally necessary traffic, which is not originally necessary. Therefore, the traffic amount is increased to thereby cause a network throughput to be deteriorated. Moreover, the change of a packet order in a real time session such as VoIP (Voice over Internet Protocol) causes deterioration in the transmission quality to an end user.
Therefore, in a router in a next generation network, it is important to allocate the same path to the packets of the same stream. Here, as a technique for allocating the same path to the packets of the same stream, a Hash-Threshold method disclosed by D. Thaler is known.
This Hash-Threshold method extracts a result after a HASH operation is carried out to flow identification data for identifying a flow included in a header of a received packet, as “Key”. A CRC16 operation and the like may be considered as an example of the Hash operation. Therefore, this operation result implies the degeneration of the flow identification data, and is used when a transfer path is allocated to the flow in the following process. Also, in the Hash-Threshold method, if N kinds of next hop routers are present, a space defined in “Key” is divided into a plurality of sub-spaces in accordance with a distribution ratio of traffic, so that regions are defined.
Therefore, a boundary value between the regions is compared with “key” that is degeneration of the flow identification data and one of the regions to which the received packet belongs is specified. Then, the packet is transferred to a next hop router corresponding to the specified region. Therefore, a load is distributed.
FIG. 3 shows a specific example of such a method. Referring to FIG. 3, there are four kinds of next hop routers as a transfer destination of a packet. A space defined in “Key” is divided into four spaces. Also, boundary values between respective spaces are 16383, 32767 and 49151. In addition, it is supposed that a value of “Key” calculated by carrying out the CRC16 operation to a bit sequence of a total of 64 bits of an IP destination address (32 bits) and an IP Src address (32 bits) serving as data for identifying a packet is 35000. In this case, the value of 35000 that is the calculated “Key” is greater than the boundary value of 32767 and less than 49151. Therefore, a transfer destination is determined to be a next hop router 3, and the packet is transferred.
Through the above-mentioned operation, the Hash-Threshold method can attain “keeping of Packet Order” in the above-mentioned end user in the configuration in which a plurality of paths are listed as candidates with regard to a certain flow. Therefore, it is ensured that the same path can be allocated to the packets of the same flow.
However, the Hash-Threshold method has several problems represented as follows.
At first, a first problem is a problem that it is difficult to attain the Hash-Threshold method at a high speed in hardware. That is, in the Hash-Threshold method, it is necessary to read out a threshold data of “(transfer destination candidate count)-1” when a transfer destination candidate is solved in accordance with a flow identification data. For this reason, if there are 32 transfer destination candidates in maximum, it is necessary to read out the threshold hold data of 31 kinds within a minimum packet process time for arrival of each packet. Therefore, it is necessary to frequently carry out a memory access. This results in a problem that its process requires a long time.
A second problem is that the number of flows cannot be suppressed in which it is necessary to change allocation paths when the increase/decrease of parallel paths and the change in a load distribution ratio between the parallel paths are induced. Here, a rate of the flows having the allocation paths to be changed to the whole flows is referred to as “deterioration rate”.
The above-mentioned problems imply that in a datagram transfer apparatus, especially, in the router for the above-mentioned next generation Internet, it is important to minimize the number of flows having the allocation path to be changed because of the increase/decrease of those parallel paths and the change in the load distribution ratio between array paths, namely, to minimize “deterioration rate”. Therefore, “keeping of packet order” in the end user is important not only to protect a deterioration of a network throughput but also to improve a communication quality to the end user.
On the contrary, the reason why the order of the packets is not kept is that the packets of the same flow reach the end user through different routes. The reason why the packets of the same flow reach the end user through the different routes is that the different paths are allocated to the packets of the same flow.
For example, in the MPLS traffic engineering, there may be a case that a predetermined load allocation to LSP is changed in order to keep a load balance in a whole network. Similarly, on a plurality of channels set in parallel, if a load distribution of the best effort traffic is attained by using a non-reservation band, there may be a case that the load distribution ratio is changed in correspondence to a variation of a reservation band.
Moreover, in a network using a future WDM (Wavelength Division Multiplex), a case is expected in which the number of parallel channels is increased because of switching between wavelength channels in accordance with a traffic variation, in addition to a reduction in the number of parallel channels caused by a communication fault or a maintenance.
In this way, the change of the load allocation to LSP, the change of the load distribution ratio to match with the variation of the reservation band, and the decrease/increase of the parallel channels cause the router to inevitably change the allocation of the path to the stream. Here, the change of the allocation of the path implies that the stream after the change is transmitted through a route different from a transmission route prior to the change. Therefore, a timing of a reception of the end user is deviated by a difference of a delay time peculiar to each route.
Therefore, naturally, when the flows for allocation paths to be changed are increased, namely, the so-called “deterioration rate” is increased, the order of the packets in the end user cannot be kept, which brings about the adverse influence such as the severe deterioration in the communication quality.
The process of the occurrence of the adverse influence in the Hash-Threshold method will be described below in detail by using the actual example shown in the drawings.
Referring to FIG. 4A, it is supposed that the equal load distribution by four next hop routers is attained to a space defined in a stream identifier. At this time, it is supposed that a fifth next hop router is newly added and the setting is changed such that the load distribution is equally carried out by the five next hop routers. In this case, the usage of the load distribution method according to the Hash-Threshold method results in the following problem. That is, besides a region in which a transfer destination is changed to a next hop router 5, the regions such as a region in which a transfer destination is changed from a next hop router 1 to a next hop router 2, a region in which a transfer destination is changed from the next hop router 2 to a next hop router 3 and a region which a transfer destination is changed from the next hop router 3 to a next hop router 4 is 30% of the whole region. Such a useless change of a transfer destination makes the transfer order of the packets impossible. This results in a problem that a throughput is largely deteriorated in the TCP traffic and the like.
If it is tried to theoretically solve the above-mentioned problems, it may be considered that the setting of regions shown in FIG. 4B can eliminate the region in which the transfer destination is uselessly changed except the next hop router 5. However, irrespectively of the existence of such theoretical concept, the reason why the above problems are present is that the Hash Threshold method directly compares the value of the boundary between the next hop routers with “Key” obtained as the operation result. For this reason, the Hash Threshold method can select the region to be allocated to one next hop router only in a continuous manner. This results in the problem of the occurrence of the unnecessarily many regions in which the transfer destination is changed. Hence, this leads to a problem of the increase of the “deterioration rate”.
In conjunction with the above description, a routing apparatus is disclosed in Japanese Laid Open Patent Application (JP-A-Heisei 7-115434). The routing apparatus in a packet telecommunication network in which a transmission route of packets from among a plurality of routes in accordance with a predetermined order of priority levels. In the routing apparatus, a first route registering section stores ones having higher priority levels of the plurality of routes in the order of higher priority levels. A second route registering section stores ones of said plurality of routes other than said routes having higher priority levels in a predetermined ratio. A first route read section reads said routes from the first route registering section in the order of priority levels every time a call is originated. A first route selecting section determines whether the route read out by the first route read section could transmit the packets, to select the route, which can transmit the packets. A second route registering section sequentially updates a read start point each time a case where a route cannot be selected by the first route selecting section occurs, and reads the routes from the second route read section in order. A second route selecting section determines whether or not the route read out by the second route read section could transmit the packets, to select the route, which can transmit the packets.
Also, a server apparatus is disclosed in Japanese Laid Open Patent Application (JP-A-Heisei 10-198642). In this reference, the server apparatus is composed of a plurality of back-end servers 12 in which server processes 21 are provided to process a request of a client. Also, the server apparatus is composed of a front-end server 11 which receives a request from the client and which includes a request transfer control mechanism 113 for transferring the received request to an appropriate ones of said back-end servers 12. The request transfer control mechanism 113 determines said appropriate back-end servers 12 to which requests from the clients to the same service should be transferred, using the identification data of the clients. Therefore, the processing of one kind of service is distributed the plurality of back-end servers to improve the processing performance.
Also, a routing method is disclosed in Japanese Laid Open Patent Application (JP-A-Heisei 11-239181). In this reference, a connectionless packet transmission network is composed of a central processor and a plurality of router units provided at a plurality of nodes and connected with the above central processor. The central processor executes a process composed of a step of previously storing a loop from each of the router units to a destination and all routes without an excessive way, of a step of calculating a distribution ratio to all of the routes to a produce a routing table, using an evaluation function which contains a delay time of the packet from a transmission origin to the destination and a usage rate of the maximum load router unit having a maximum load in the packet transmission network, such that the value of the evaluation function is smaller, and of a step of transmits the routing table to each of the router units. Each of the router units executes a process composed of a step of storing the routing table transmitted from the central processor and of a step of routing an input packet using the stored routing table.